package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LCIT0812 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public List<List<String>> solveNQueens(int n) {
            int[] status = new int[n];
            List<List<String>> ans = new ArrayList<>();
            dfs(n, 0, status, new ArrayList<>(), ans);
            return ans;
        }

        public void dfs(int n, int row, int[] status, List<String> curPath, List<List<String>> ans) {
            if (row >= n) {
                ans.add(copy(curPath));
                return;
            }

            for (int i = 0; i < n; i++) {
                if (status[i] == 0 && check(curPath, row, i, n)) {
                    StringBuilder curRow = new StringBuilder();
                    for (int j = 0; j < n; j++) {
                        if (j == i) curRow.append("Q");
                        else curRow.append(".");
                    }
                    curPath.add(curRow.toString());
                    status[i] = 1;
                    dfs(n, row + 1, status, curPath, ans);
                    status[i] = 0;
                    curPath.remove(curPath.size() - 1);
                }
            }
        }

        public boolean check(List<String> curPath, int row, int col, int n) {
            for (int i = 1; row - i >= 0 && col - i >= 0; i++) {
                if (curPath.get(row - i).charAt(col - i) == 'Q') return false;
            }

            for (int i = 1; row - i >= 0 && col + i < n; i++) {
                if (curPath.get(row - i).charAt(col + i) == 'Q') return false;
            }

            return true;
        }

        public List<String> copy(List<String> curPath) {
            List<String> copyPath = new ArrayList<>();
            for (String s : curPath) {
                copyPath.add(new StringBuilder(s).toString());
            }
            return copyPath;
        }
    }

    // 1. 记录每一列，在第几行放了皇后；递归的每一层代表每一行；保证每个皇后的行与列都不相同。
    // 2. 只需要判断对角线上是否为单皇后。
    class Solution_Other {
        private List<List<String>> lists = new ArrayList();

        public List<List<String>> solveNQueens(int n) {
            if (n == 0) return lists;

            // 标记数组
            int[] b = new int[n];
            // 棋盘
            char[][] s = new char[n][n];
            // 填充标记数组
            Arrays.fill(b, Integer.MIN_VALUE);
            // 填充棋盘
            for (int i = 0; i < n; i++) Arrays.fill(s[i], '.');
            dfs(0, n, b, s);
            return lists;
        }

        void dfs(int index, int n, int[] b, char[][] s) {
            // 皇后已经全部放置
            if (index == n) {
                List<String> list = new ArrayList();
                for (char[] ss : s) list.add(String.valueOf(ss));
                lists.add(new ArrayList(list));
            }

            for (int i = 0; i < n; i++) {
                // 该列已经有皇后
                if (b[i] != Integer.MIN_VALUE) continue;

                boolean flag = false;
                // 判断左侧对角线
                int j = i - 1;
                while (j >= 0) {
                    int t = i - j;
                    if (b[j] == index + t || b[j] == index - t) {
                        flag = true;
                        break;
                    }
                    j--;
                }
                if (flag) continue;

                // 判断右侧对角线
                j = i + 1;
                while (j < n) {
                    int t = j - i;
                    if (b[j] == index + t || b[j] == index - t) {
                        flag = true;
                        break;
                    }
                    j++;
                }
                // 对角线上已经有皇后
                if (flag) continue;

                // 此列此行可以放皇后
                b[i] = index;
                s[index][i] = 'Q';
                dfs(index + 1, n, b, s);
                b[i] = Integer.MIN_VALUE;
                s[index][i] = '.';
            }
        }
    }

    public void run() {
//        System.out.println(new Solution().solveNQueens(4));
        System.out.println(new Solution().solveNQueens(5));
        System.out.println(new Solution_Other().solveNQueens(5));
    }

    public static void main(String[] args) throws Exception {
        LCIT0812 an = new LCIT0812();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
